/*这里是自守数的第三版，运行正确。
    前两版会超时的原因是：题目要求给的是求出0~n以内的自守数，但n给了很多个，前两版每次都要从0开始从新判断，所以会超时
    这里直接用了一个数组来存放前n个数共有多少个自守数：cnt[n]=5 --> 前n个数里面有5个自守数
        再让 cnt[n+1]=cnt[n]，直接将n个数里面的自守数的个数赋给 n+1，此时只用判断 n+1 是否为自守数就行了
*/
#include<stdio.h>
#define maxN 100005 
int cnt[maxN];//cnt数组用来存放一个数以内自守数的个数 
int main()
{
    int N, M, MOD, i, k;
    cnt[0] = 1;   // 0为自守数，故 0以内自守数的个数为1 
    cnt[1] = 2;   //0和1为自守数，故 1以内自守数的个数为2
    for (i = 2; i < maxN; i++)
    {
        cnt[i] = cnt[i - 1];//将cnt[i-1]的值赋给cnt[i],此时只用判断i是否为自守数即可得到i以内（包括i） 的自守数个数 
        k = i;
        MOD = 1;
        while (k)
        {
            MOD = MOD * 10;//随着while循环的执行，MOD的位数在不断增加 
            k = k / 10;//通过k的位数（也就是i的位数）来判断while循环执行的次数 
        }
        if ((i * i) % MOD == i) //判断i平方的尾数与i是否相等，即判断i是否为自守数 
            cnt[i] ++;//如果i为自守数，则cnt[i]=cnt[i-1]+1 
    }
    scanf("%d", &M);         //输入要求M个数以内的自守数 
    int a[M];           
    for (i = 0; i < M; i++)//利用for，循环依次输入前M个数 
        scanf("%d", &a[i]);
    for (i = 0; i < M ; i++)
    {
        if (i != M - 1)
            printf("%d ", cnt[a[i]]);// 用printf依次输出前M-1个数各自以内的自守数个数 ，注意：每个数之间要有空格 
        else
            printf("%d\n", cnt[a[i]]);//最后一个数后没有空格 
    }
    return 0;
}







